from play_order.base_strategy import PlayOrderStrategy
from entity.player import Player
from entity.card import Card
from entity.game import TurnResolver, ILLEGAL

class RuleBasedStrategy(PlayOrderStrategy):
    def __init__(self, resolver: TurnResolver):
        """
        支持传入一个 TurnResolver 实例，以当前状态继续求最优牌序。
        """
        self.resolver = resolver

    def get_optimal_play_order(self, player: Player) -> tuple:
        """
        基于回溯法求最优出牌顺序：
          - 利用原地交换的方式生成排列，避免每次构造候选列表和当前序列的拷贝；
          - 采用递归，每次固定位置 start，尝试将 hand[start] 与后续元素交换；
          - 每次在当前位置使用当前牌（hand[start]），克隆结算器状态 resolver_state，调用 resolve 进行结算；
          - 若结算失败，则不再继续递归，并更新最佳结果为当前已成功结算的前缀；
          - 若结算成功，则累加得分，并递归处理下一个位置；
          - 最终返回最佳牌序（部分或全部排列）及最高得分。
          
        返回一个二元组：(最佳出牌顺序列表, 最高得分)。
        """
        # 用于回溯的手牌，复制一份，避免直接修改玩家手牌
        hand = player.hand.copy()
        best_order = []   # 存储最佳出牌顺序（前缀排列）
        best_score = 0    # 存储最高得分

        # 初始结算器状态
        resolver_state = self.resolver

        def backtrack(start, current_score, current_resolver):
            nonlocal best_order, best_score, hand

            # 剪枝条件：当前得分 + 剩余牌数（最乐观情况下每牌+1）不足以超过当前最高分时提前返回
            if current_score + (len(hand) - start) < best_score:
                return

            # 当 start 到达手牌末尾，说明所有牌均已安排
            if start == len(hand):
                if current_score > best_score:
                    best_score = current_score
                    best_order = hand.copy()
                return

            # 从 start 到末尾依次交换，构造排列
            for i in range(start, len(hand)):
                # 交换，确保 hand[0:start] 为当前已确定的出牌顺序
                hand[start], hand[i] = hand[i], hand[start]
                # 克隆当前 resolver 状态，保证每个分支独立
                resolver_clone = current_resolver.clone()
                # 尝试结算当前位置的牌
                result = resolver_clone.resolve(hand[start])
                if result == ILLEGAL:
                    # 结算失败：更新最佳结果为当前已确定的顺序（前缀 hand[0:start]）
                    if current_score > best_score:
                        best_score = current_score
                        best_order = hand[:start].copy()
                else:
                    # 结算成功：累加得分，并递归处理下一个位置
                    new_score = current_score + result
                    backtrack(start + 1, new_score, resolver_clone)
                # 回溯恢复交换状态
                hand[start], hand[i] = hand[i], hand[start]

        backtrack(0, 0, resolver_state)
        return best_order, best_score
